package 力扣.队列.单调队列;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class 跳跃游戏VI_1696 {
    public static void main(String[] args) {
        int[] ints = {1,-5,-20,4,-1,3,-6,-3};
//        int[] ints = {1,-1,-2,4,-7,3};
        int k = 2;
        int i = maxResult3(ints, k);
        System.out.println(i);
    }

    /**
     * 顺着走不行，我们就假设
     *超时版：时间复杂度O(nk)
     * 方法一：动态规划：对于任意一个位置，它所在金币的最大值，肯定是由：de[i] = Max(dp[i-1].........dp[i-k]) + nums[i]
     *        采用数组接收
     */
    public static int maxResult(int[] nums, int k) {
        int[] ints = new int[nums.length];////每个位置上金币收集的数目
        ints[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int te = nums[i];
            int pre = Math.max(i - k, 0);
            int max = Integer.MIN_VALUE;
            for (int j = pre; j < i; j++) {
                max = Math.max(ints[j],max);
            }
            ints[i] = te + max;
        }
        return ints[nums.length - 1];
    }
    /**
     * 方法二：固定滑动窗口
     * 我们进行dp递推的时候，发现递推的窗口是固定的,只要在窗口中找到最大值即可，可用滑动窗口最大值来实现（单调队列）
       单调队列：
     */
    public static int maxResult2(int[]nums,int k){
        int len = nums.length;
        int[] ints = new int[len];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            int te = nums[i];
            int teMax = 0;

            //入队
            if (!deque.isEmpty()){
                teMax =  deque.getFirst();
            }
            ints[i] = ints[teMax] + te;
            while (!deque.isEmpty() && ints[deque.getLast()] < ints[i]){//保证单调队列
                deque.pollLast();
            }
            deque.offerLast(i);

            //出队
            if (i >= k){
                while (!deque.isEmpty() && deque.getFirst() < i - k + 1){//保证队列的元素还在窗口中
                    deque.pollFirst();
                }
            }
        }
        return ints[len - 1];
    }

//  单调队列
    public static int maxResult3(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int len = nums.length;
       int[] ans = new int[len];
       ans[0] = nums[0];
       deque.add(0);
        for (int i = 1; i < nums.length; i++) {
            //出队
            if (i >= k){
                while (!deque.isEmpty() && deque.peekFirst() < (i - k)){
                    deque.pollFirst();
                }
            }

            //入队
            ans[i] = ans[deque.peekFirst()] + nums[i];
            while (!deque.isEmpty() && ans[deque.peekLast()] < ans[i]){
                deque.pollLast();
            }
            deque.offerLast(i);

        }
        return ans[len - 1];
    }
    //优先队列
    public static int maxResult4(int[] nums, int k) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        PriorityQueue<Integer[]> pq = new PriorityQueue<>(new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return o2[1] - o1[1];//0:索引 1：值
            }
        });
        int len = nums.length;
        int[] ans = new int[len];
        ans[0] = nums[0];//千万别忘记给ans[0] 进行初始化
        pq.offer(new Integer[]{0,ans[0]});
        for (int i = 1; i < len; i++) {
            if (i > k){
                while (!pq.isEmpty() && pq.peek()[0] < (i - k)){
                    pq.poll();
                }
            }
            ans[i] = pq.peek()[1] + nums[i];
            pq.offer(new Integer[]{i,ans[i]});
        }
        return ans[len - 1];
    }

    public int maxResult5(int[] nums, int k) {//单调队列
        if (nums == null || nums.length == 0){
            return 0;
        }
        Deque<Integer[]> deque = new LinkedList<>();//单调递减队列
        int N = nums.length;
        int[] ans = new int[N];
        ans[0] = nums[0];//千万别忘记初始化了！！！
        deque.offerFirst(new Integer[]{0,ans[0]});
        for (int i = 1; i < N; i++) {
            int te = nums[i];
            if (i > k){//出队
                while (!deque.isEmpty() && deque.peekFirst()[0] < (i - k)){
                    deque.pollFirst();
                }
            }
            ans[i] = deque.peekFirst()[1] + te;
            //入队要保证单调性！！！
            while (!deque.isEmpty() && deque.peekLast()[1] < ans[i]){
                deque.pollLast();
            }
            deque.offerLast(new Integer[]{i,ans[i]});
        }
        return ans[N - 1];
    }
}
